/**
 *  @file dijkstra.c
 *  @brief Dijkstra's algorithm
 *  for both MST and shortest path; the animation asks which at the
 *  beginning.  Based on prim.c, created June 1990, and subsumes it.
 * @author Matt Stallmann
 * @date March 2005
 * <br>$Id: dijkstra.c 10 2007-06-28 20:08:57Z mfms $
 */

/*
 *  Copyright (C) 2005  Matthias Stallmann.
 *  Contact: matt_stallmann@ncsu.edu
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program (file COPYING.txt); if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA.
 */

#include<stdio.h>
#include<limits.h>
#include "Gdr.h"

edge candidate[MAX_VERTEX];   /* candidate edge for this vertex */
int cost[MAX_VERTEX];      /* cost of the candidate edge */
int status[MAX_VERTEX];    /* status of this vertex -- use defines below */
#define in_tree 0
#define unseen 1
#define fringe 2

/* declarations and macros for the animation */
#define MSG_SIZE 100            /* maximum length of a message */
char msg[MSG_SIZE];
TWIN pwin;                      /* window for user prompts */
#define XW 1                    /* prompt window coordinates */
#define YW 1
#define init_prompt_window (pwin = create_text_window(XW,YW,""))
#define destroy_prompt_window (kill_window(pwin))
#define wait(msg) (write_text_window(pwin,msg),suspend_animation(),\
               hide_window(pwin))
#define COUNT 4

typedef struct cell {
  struct cell *next;
  vertex vx;
} *V_LIST;
V_LIST fringe_list = NULL;

void add_to_fringe_list(vertex v)
{
  V_LIST new_item;
  
  new_item = (V_LIST)calloc(1,sizeof(struct cell));
  new_item->next = fringe_list;
  new_item->vx = v;
  fringe_list = new_item;
}

void remove_from_fringe_list(V_LIST prev)
     /* pointer to cell before the one being removed;
                  NULL if first cell is to be removed */
{
  V_LIST out = (prev == NULL) ? fringe_list : prev->next;
  if (prev == NULL) 
    fringe_list = fringe_list->next;
  else
    prev->next = out->next;
  free(out);
}

int weight( edge e )            /* returns value of integer label */
           
{
  int wt;
  char * el = edge_label( e );
  int got_it = sscanf( el, "%d", &wt );
  if( got_it != 1 ) {
    wt = 0;
  }
  free( el );
  return( wt );
}

char *new_string(int i) /* returns a string representation of integer i */
          
{
  char *stg;
  stg = (char *)calloc(10,sizeof(char));
  sprintf(stg,"%d",i);
  return (stg);
}

void animat(void)
{
  vertex x;                     /* current vertex */
  V_LIST x_pos;                 /* x's position in the fringe list */
  int edge_count = 0;           /* number of edges in tree */
  vertex y;                     /* generic vertex for loops */
  edge e;                       /* generic edge */
  int num_vertices = 0;         /* number of valid vertices */
  int cost_to_connect;          /* cost for vertex to connect via the current
                                   edge */
  int min_cost;                 /* minimum cost in current iteration */
  int total_cost;               /* total cost of MST */
  V_LIST prev,ptr;              /* generic pointers to fringe list */
  char answer[ MSG_SIZE ];
  int mst = 0;                  /* != 0 if doing mst */
  
  
  init_prompt_window;
  query( 0, 0, "MST or SSSP? (t/p)? ", answer );
  if( answer[ 0 ] == 't' ) {
    mst = 1;
    wait("Starting MST with vertex 0\nClick Resume? to begin");
  }
  else {
    mst = 0;
    wait("Starting SSSP with vertex 0\nClick Resume? to begin");
  }
  
  /* hide labels on all edges */
  for_all_edges( e ) {
    hide_edge_label( e );
    un_highlight_edge( e );
    display_edge( e );
  }
  
  /* initialize status/display and count number of valid vertices */
  for_all_vertices( y ) {
    status[y] = unseen;
    un_highlight_vertex( y );
    hide_vertex_label( y );
    ++num_vertices;
  }
  
  
  total_cost = 0;
  x = get_a_vertex();
  status[x] = in_tree;
  cost[x] = 0;
  highlight_vertex(x);
  
  while ( edge_count < num_vertices - 1 ) {
    /* traverse adjacency list for x */
    for (e = first_out_edge(x); e != NULL_EDGE;
         e = next_out_edge(x,e)) {
      y = other_vertex(x,e);
      if (status[y] == fringe) {
        expose_edge_label(e);
        cost_to_connect = mst ? weight(e) : cost[x] + weight(e);
        if (cost_to_connect < cost[y]) {
          /* y has a new candidate edge */
          change_vertex_label(y,new_string(cost_to_connect));
          un_highlight_edge( candidate[ y ] );
          candidate[y] = e;
          highlight_edge(e);
          cost[y] = cost_to_connect;
        }
      }
      if (status[y] == unseen) {
        /* y is a new fringe vertex */
        cost_to_connect = mst ? weight(e) : cost[x] + weight(e);
        highlight_edge(e);
        expose_edge_label(e);
        change_vertex_label(y,new_string(cost_to_connect));
        expose_vertex_label(y);
      
        status[y] = fringe;
        add_to_fringe_list(y);
        candidate[y] = e;
        cost[y] = cost_to_connect;
      }
    } /* end of adjacency list traversal */
   
    wait("Ready to choose next tree edge\nClick Resume to continue");
   
    /* choose next tree edge (find lowest cost fringe vertex) */
    if (fringe_list == NULL) {
      printf("Graph is not connected\n");
      return;
    }
   
    min_cost = INT_MAX;
    for (ptr = fringe_list, prev = NULL;
         ptr != NULL; prev = ptr, ptr = ptr->next) {
      if (cost[ptr->vx] < min_cost) {
        min_cost = cost[ptr->vx];
        x = ptr->vx;
        x_pos = prev;
      }
    }        /* x is lowest cost vertex on fringe list */
    if( mst ) {
      total_cost = total_cost + min_cost;
    }
    remove_from_fringe_list(x_pos);
    status[x] = in_tree;
    edge_count++;
   
    blink_edge(candidate[x],COUNT);
    un_highlight_edge(candidate[x]);
    highlight_vertex(x);
    if( mst ) {
      hide_edge_label(candidate[x]);
      hide_vertex_label(x);
    }
   
    /* remove redundant edges */
    for (e = first_out_edge(x); e != NULL_EDGE;
         e = next_out_edge(x,e)) {
      y = other_vertex(x,e);
      if (status[y] == in_tree && !are_edges_equal(candidate[x],e)) {
        /* edge xy is redundant */
        hide_edge(e);
      }
    }
  }   /* end of main loop */
  
  /* expose labels on all displayed (tree) edges and highlight them,
     while showing other edges */
  for (e = first_edge(); e != NULL_EDGE; e = next_edge(e)) {
    if (is_displayed_edge(e)) {
      expose_edge_label(e);
      highlight_edge(e);
    }
    else {
      hide_edge_label(e);
      un_highlight_edge(e);
      display_edge(e);
    }
  }
  
  /* display total cost of MST */
  if( mst ) {
    sprintf(msg,"Total cost = %d\n Click RESUME ? to end animation",
            total_cost);
    wait(msg);
  }
  else {
    wait("This is the shortest path tree\n Click RESUME ? to end animation");
  }
} /* animat ends */

/*  [Last modified: 2007 06 28 at 19:46:11 GMT] */
